package leetcode.recursive;

/**
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 * <p>
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 * <p>
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 * <p>
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 示例 2：
 * <p>
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 * 示例 3：
 * <p>
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 * 示例 4：
 * <p>
 * 输入：s = "abc3[cd]xyz"
 * 输出："abccdcdcdxyz"
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 30
 * s 由小写英文字母、数字和方括号 '[]' 组成
 * s 保证是一个 有效 的输入。
 * s 中所有整数的取值范围为 [1, 300]
 */

public class LeetCode394_DecodeString {
    public String decodeString(String s) {
//        return f(s);
        return f2(s, 0);
    }

    static int cur = 0;

    public String f(String s) {
        StringBuilder sb = new StringBuilder();
        String segStr = null;
        int times = 0;
        while (cur < s.length()) {
            char ch = s.charAt(cur++);
            if ('1' <= ch && '9' >= ch) {
                times = times * 10 + ch - '0';
            } else if (ch == '[') {
                segStr = f(s);
                if (times > 0) {
                    sb.append(String.valueOf(segStr).repeat(times));
                }
                times = 0;
            } else if ('a' <= ch && 'z' >= ch) {
                sb.append(ch);
            } else if (ch == ']') {
                return sb.toString();
            }
        }
        if (times > 0) {
            sb.append(String.valueOf(segStr).repeat(times));
        }
        return sb.toString();
    }

    public String f2(String s, int i) {
        StringBuilder sb = new StringBuilder();
        int times = 0;
        while (i < s.length() && s.charAt(i) != ']') {
            char ch = s.charAt(i++);
            if ('0' <= ch && '9' >= ch) {
                times = times * 10 + ch - '0';
            } else if (ch == '[') {
                sb.append(get(times, f2(s, i)));
                i = cur + 1;
                times = 0;
            } else {
                sb.append(ch);
            }
        }
        cur = i;
        return sb.toString();
    }

    public static String get(int cnt, String str) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < cnt; i++) {
            builder.append(str);
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        LeetCode394_DecodeString leetCode394_decodeString = new LeetCode394_DecodeString();
//        System.out.println(leetCode394_decodeString.decodeString("3[a]2[b]"));
//        System.out.println(leetCode394_decodeString.decodeString("2[abc]3[cd]ef"));
//        System.out.println(leetCode394_decodeString.decodeString("2[abc]3[c2[d]]"));
        System.out.println(leetCode394_decodeString.decodeString("100[leetcode]"));
    }
}
